package fireway;

/**
 * 再哈希法
 */
public class HashDoubleTable {
    private DataItem[] mHashArray;

    private int mArraySize;

    public HashDoubleTable(int size) {
        mArraySize = size;
        mHashArray = new DataItem[mArraySize];
    }

    public void insert(DataItem item) {
        int data = item.getData();

        int hash = hashFunc1(data);
        int step = hashFunc2(data);

        while (mHashArray[hash] != null) {
            hash += step;
            hash %= mArraySize;
        }

        mHashArray[hash] = item;
    }

    public DataItem delete(int data) {
        int hash = hashFunc1(data);
        int step = hashFunc2(data);

        while (mHashArray[hash] != null) {
            if (data == mHashArray[hash].getData()) {
                DataItem tmp = mHashArray[hash];
                mHashArray[hash] = null;
                return tmp;
            }
            hash += step;
            hash %= mArraySize;
        }

        return null;
    }

    public DataItem find(int data) {
        int hash = hashFunc1(data);
        int step = hashFunc2(data);

        while (mHashArray[hash] != null) {
            if (data == mHashArray[hash].getData()) {
                return mHashArray[hash];
            }
            hash += step;
            hash %= mArraySize;
        }

        return null;
    }

    @Override
    public String toString() {
        StringBuilder b = new StringBuilder();

        b.append('[');
        for (int i = 0; i < mArraySize; i++) {
            if (null == mHashArray[i]) {
                b.append("null");
            } else {
                b.append(mHashArray[i].getData());
            }

            if (i == mArraySize - 1) {
                b.append("]");
            } else {
                b.append(", ");
            }
        }

        return b.toString();
    }

    private int hashFunc1(int data) {
        return data % mArraySize;
    }

    /**
     * <p>第二个哈希函数取下面的形式会比较好</p>
     * <p>step = constant - (key % constant);</p>
     * <p>其中constant是质数，且小于数组容量。</p>
     */
    private int hashFunc2(int data) {
        return 5 - data % 5;
    }
}

